package com.cuz.daileetcode;

import java.util.LinkedList;

public class Day52 {
    public static class ArraySplitDiffBetweenLeftRightMaxValues {
        static int diffMaxValueOf(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return 0;
            }
            int max = Integer.MIN_VALUE;
            for (int item : arr) {
                max = Math.max(max, item);
            }
            return Math.max(max - arr[0], max - arr[arr.length - 1]);
        }
    }


    public static class ReceiveRainwater {

        public static void main(String[] args) {
            int[] ints = {3, 2, 5, 1, 1, 4, 6, 7, 8, 1, 1, 1, 5, 6, 2, 3, 1, 1, 2};
            System.out.println(solution1(ints));
            System.out.println(solution2(ints));
            System.out.println(solution3(ints));
        }

        static int solution1(int[] arr) {
            if (arr == null || arr.length < 3) {
                return 0;
            }
            LinkedList<Integer> help = new LinkedList<>();
            int sum = 0;
            for (int index = 0; index < arr.length; index++) {
                int item = arr[index];
                if (help.size() == 0) {
                    help.add(item);
                } else {
                    Integer last = help.getLast();
                    if (item <= last) {
                        help.add(item);
                    } else {
                        if (index + 1 < arr.length && arr[index + 1] > item) {
                            help.add(item);
                        } else {
                            //第一个
                            Integer first = help.removeFirst();
                            while (!help.isEmpty()) {
                                //要计算积水的
                                Integer temp = help.removeFirst();
                                sum += Math.max(0, Math.min(item, first) - temp);
                            }
                            if (first > item) {
                                help.add(first);
                            }
                            help.add(item);
                        }
                    }
                }
            }

            return sum;
        }


        static int solution2(int[] arr) {
            if (arr == null || arr.length < 3) {
                return 0;
            }
            int len = arr.length;
            int[] leftHighest = new int[len];
            int[] rightHighest = new int[len];
            for (int index = 1; index < arr.length; index++) {
                leftHighest[index] = Math.max(arr[index - 1], leftHighest[index - 1]);
            }
            for (int index = arr.length - 2; index >= 0; index--) {
                rightHighest[index] = Math.max(arr[index + 1], rightHighest[index + 1]);
            }
            int sum = 0;
            for (int index = 0; index < arr.length; index++) {
                int boundary = Math.min(leftHighest[index], rightHighest[index]);
                if (boundary > arr[index]) {
                    sum += boundary - arr[index];
                }
            }
            return sum;
        }


        static int solution3(int[] arr) {
            if (arr == null || arr.length < 3) {
                return 0;
            }
            int leftMax = arr[0];
            int len = arr.length;
            int rightMax = arr[len - 1];
            int leftIndex = 1;
            int rightIndex = len - 2;
            int sum = 0;
            while (leftIndex <= rightIndex) {
                int boundary = Math.min(rightMax, leftMax);
                if (leftMax <= rightMax) {
                    sum += Math.max(0, boundary - arr[leftIndex]);
                    leftMax = Math.max(arr[leftIndex], leftMax);
                    leftIndex++;
                } else {
                    sum += Math.max(0, boundary - arr[rightIndex]);
                    rightMax = Math.max(arr[rightIndex], rightMax);
                    rightIndex--;
                }
            }
            return sum;
        }

    }
}
